﻿using System;
using System.Collections.Generic;
using System.Numerics;
using System.Threading;

namespace Combina.Core
{
    public static class Choose
    {
        public const int MaxN64 = 67;

        public static ulong Calculate64(int n, int k)
        {
            if (n < 0)
                throw new ArgumentOutOfRangeException("n", n, "Must be non-negative");

            if (k < 0)
                throw new ArgumentOutOfRangeException("k", k, "Must be non-negative");

            if (k == 0)
                return 1;

            if (n == 0)
                return 0;

            if (n <= Factorial.MaxN64)
                return (Factorial.Calculate64(n) / (Factorial.Calculate64(k) * Factorial.Calculate64(n - k)));

            if (k > n / 2)
                return Calculate64(n, n - k);

            int nStart = Math.Max(Factorial.MaxN64, k * 2 - 1);
            return _choose64[k - 1][n - nStart - 1];
        }

        public static BigInteger Calculate(int n, int k)
        {
            if (n <= MaxN64)
                return Calculate64(n, k);

            if (k < 0)
                throw new ArgumentOutOfRangeException("k", k, "Must be non-negative");

            if (k == 0)
                return 1;

            if (k > n / 2)
                return Calculate(n, n - k);

            int nStart = Math.Max(MaxN64, k * 2 - 1);
            _lock.EnterReadLock();
            try
            {
                if (k < _bigIntegerValues.Count)
                {
                    List<BigInteger> kList = _bigIntegerValues[k - 1];
                    if (n - nStart <= kList.Count)
                        return kList[n - nStart - 1];
                }
            }
            finally
            {
                _lock.ExitReadLock();
            }

            BigInteger value = Calculate(n - 1, k - 1) + Calculate(n - 1, k);

            _lock.EnterUpgradeableReadLock();
            try
            {
                if (k > _bigIntegerValues.Count)
                {
                    _lock.EnterWriteLock();
                    try
                    {
                        while (k > _bigIntegerValues.Count)
                            _bigIntegerValues.Add(new List<BigInteger>());

                        _bigIntegerValues[k - 1].Add(value);
                    }
                    finally
                    {
                        _lock.ExitWriteLock();
                    }
                }
                else
                {
                    List<BigInteger> kList = _bigIntegerValues[k - 1];
                    if (n - nStart > kList.Count)
                    {
                        _lock.EnterWriteLock();
                        try
                        {
                            kList.Add(value);
                        }
                        finally
                        {
                            _lock.ExitWriteLock();
                        }
                    }
                }
            }
            finally
            {
                _lock.ExitUpgradeableReadLock();
            }
            return value;
        }

        private static readonly ulong[][] _choose64 = new[]
                                                          {
                                                              new ulong[]
                                                                  {
                                                                      21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34
                                                                      , 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
                                                                      48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61
                                                                      , 62, 63, 64, 65, 66, 67,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      210, 231, 253, 276, 300, 325, 351, 378, 406, 435, 465,
                                                                      496, 528, 561, 595, 630, 666, 703, 741, 780, 820, 861,
                                                                      903, 946, 990, 1035, 1081, 1128, 1176, 1225, 1275,
                                                                      1326, 1378, 1431, 1485, 1540, 1596, 1653, 1711, 1770,
                                                                      1830, 1891, 1953, 2016, 2080, 2145, 2211,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      1330, 1540, 1771, 2024, 2300, 2600, 2925, 3276, 3654,
                                                                      4060, 4495, 4960, 5456, 5984, 6545, 7140, 7770, 8436,
                                                                      9139, 9880, 10660, 11480, 12341, 13244, 14190, 15180,
                                                                      16215, 17296, 18424, 19600, 20825, 22100, 23426, 24804
                                                                      , 26235, 27720, 29260, 30856, 32509, 34220, 35990,
                                                                      37820, 39711, 41664, 43680, 45760, 47905,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475,
                                                                      23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905
                                                                      , 66045, 73815, 82251, 91390, 101270, 111930, 123410,
                                                                      135751, 148995, 163185, 178365, 194580, 211876, 230300
                                                                      , 249900, 270725, 292825, 316251, 341055, 367290,
                                                                      395010, 424270, 455126, 487635, 521855, 557845, 595665
                                                                      , 635376, 677040, 720720, 766480,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      20349, 26334, 33649, 42504, 53130, 65780, 80730, 98280
                                                                      , 118755, 142506, 169911, 201376, 237336, 278256,
                                                                      324632, 376992, 435897, 501942, 575757, 658008, 749398
                                                                      , 850668, 962598, 1086008, 1221759, 1370754, 1533939,
                                                                      1712304, 1906884, 2118760, 2349060, 2598960, 2869685,
                                                                      3162510, 3478761, 3819816, 4187106, 4582116, 5006386,
                                                                      5461512, 5949147, 6471002, 7028847, 7624512, 8259888,
                                                                      8936928, 9657648,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      54264, 74613, 100947, 134596, 177100, 230230, 296010,
                                                                      376740, 475020, 593775, 736281, 906192, 1107568,
                                                                      1344904, 1623160, 1947792, 2324784, 2760681, 3262623,
                                                                      3838380, 4496388, 5245786, 6096454, 7059052, 8145060,
                                                                      9366819, 10737573, 12271512, 13983816, 15890700,
                                                                      18009460, 20358520, 22957480, 25827165, 28989675,
                                                                      32468436, 36288252, 40475358, 45057474, 50063860,
                                                                      55525372, 61474519, 67945521, 74974368, 82598880,
                                                                      90858768, 99795696,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      116280, 170544, 245157, 346104, 480700, 657800, 888030
                                                                      , 1184040, 1560780, 2035800, 2629575, 3365856, 4272048
                                                                      , 5379616, 6724520, 8347680, 10295472, 12620256,
                                                                      15380937, 18643560, 22481940, 26978328, 32224114,
                                                                      38320568, 45379620, 53524680, 62891499, 73629072,
                                                                      85900584, 99884400, 115775100, 133784560, 154143080,
                                                                      177100560, 202927725, 231917400, 264385836, 300674088,
                                                                      341149446, 386206920, 436270780, 491796152, 553270671,
                                                                      621216192, 696190560, 778789440, 869648208,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      203490, 319770, 490314, 735471, 1081575, 1562275,
                                                                      2220075, 3108105, 4292145, 5852925, 7888725, 10518300,
                                                                      13884156, 18156204, 23535820, 30260340, 38608020,
                                                                      48903492, 61523748, 76904685, 95548245, 118030185,
                                                                      145008513, 177232627, 215553195, 260932815, 314457495,
                                                                      377348994, 450978066, 536878650, 636763050, 752538150,
                                                                      886322710, 1040465790, 1217566350, 1420494075,
                                                                      1652411475, 1916797311, 2217471399, 2558620845,
                                                                      2944827765, 3381098545, 3872894697, 4426165368,
                                                                      5047381560, 5743572120, 6522361560,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      293930, 497420, 817190, 1307504, 2042975, 3124550,
                                                                      4686825, 6906900, 10015005, 14307150, 20160075,
                                                                      28048800, 38567100, 52451256, 70607460, 94143280,
                                                                      124403620, 163011640, 211915132, 273438880, 350343565,
                                                                      445891810, 563921995, 708930508, 886163135, 1101716330
                                                                      , 1362649145, 1677106640, 2054455634, 2505433700,
                                                                      3042312350, 3679075400, 4431613550, 5317936260,
                                                                      6358402050, 7575968400, 8996462475, 10648873950,
                                                                      12565671261, 14783142660, 17341763505, 20286591270,
                                                                      23667689815, 27540584512, 31966749880, 37014131440,
                                                                      42757703560,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      352716, 646646, 1144066, 1961256, 3268760, 5311735,
                                                                      8436285, 13123110, 20030010, 30045015, 44352165,
                                                                      64512240, 92561040, 131128140, 183579396, 254186856,
                                                                      348330136, 472733756, 635745396, 847660528, 1121099408
                                                                      , 1471442973, 1917334783, 2481256778, 3190187286,
                                                                      4076350421, 5178066751, 6540715896, 8217822536,
                                                                      10272278170, 12777711870, 15820024220, 19499099620,
                                                                      23930713170, 29248649430, 35607051480, 43183019880,
                                                                      52179482355, 62828356305, 75394027566, 90177170226,
                                                                      107518933731, 127805525001, 151473214816, 179013799328
                                                                      , 210980549208, 247994680648,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      705432, 1352078, 2496144, 4457400, 7726160, 13037895,
                                                                      21474180, 34597290, 54627300, 84672315, 129024480,
                                                                      193536720, 286097760, 417225900, 600805296, 854992152,
                                                                      1203322288, 1676056044, 2311801440, 3159461968,
                                                                      4280561376, 5752004349, 7669339132, 10150595910,
                                                                      13340783196, 17417133617, 22595200368, 29135916264,
                                                                      37353738800, 47626016970, 60403728840, 76223753060,
                                                                      95722852680, 119653565850, 148902215280, 184509266760,
                                                                      227692286640, 279871768995, 342700125300, 418094152866
                                                                      , 508271323092, 615790256823, 743595781824,
                                                                      895068996640, 1074082795968, 1285063345176,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      2704156, 5200300, 9657700, 17383860, 30421755,
                                                                      51895935, 86493225, 141120525, 225792840, 354817320,
                                                                      548354040, 834451800, 1251677700, 1852482996,
                                                                      2707475148, 3910797436, 5586853480, 7898654920,
                                                                      11058116888, 15338678264, 21090682613, 28760021745,
                                                                      38910617655, 52251400851, 69668534468, 92263734836,
                                                                      121399651100, 158753389900, 206379406870, 266783135710
                                                                      , 343006888770, 438729741450, 558383307300,
                                                                      707285522580, 891794789340, 1119487075980,
                                                                      1399358844975, 1742058970275, 2160153123141,
                                                                      2668424446233, 3284214703056, 4027810484880,
                                                                      4922879481520, 5996962277488,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      10400600, 20058300, 37442160, 67863915, 119759850,
                                                                      206253075, 347373600, 573166440, 927983760, 1476337800
                                                                      , 2310789600, 3562467300, 5414950296, 8122425444,
                                                                      12033222880, 17620076360, 25518731280, 36576848168,
                                                                      51915526432, 73006209045, 101766230790, 140676848445,
                                                                      192928249296, 262596783764, 354860518600, 476260169700
                                                                      , 635013559600, 841392966470, 1108176102180,
                                                                      1451182990950, 1889912732400, 2448296039700,
                                                                      3155581562280, 4047376351620, 5166863427600,
                                                                      6566222272575, 8308281242850, 10468434365991,
                                                                      13136858812224, 16421073515280, 20448884000160,
                                                                      25371763481680,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      40116600, 77558760, 145422675, 265182525, 471435600,
                                                                      818809200, 1391975640, 2319959400, 3796297200,
                                                                      6107086800, 9669554100, 15084504396, 23206929840,
                                                                      35240152720, 52860229080, 78378960360, 114955808528,
                                                                      166871334960, 239877544005, 341643774795, 482320623240
                                                                      , 675248872536, 937845656300, 1292706174900,
                                                                      1768966344600, 2403979904200, 3245372870670,
                                                                      4353548972850, 5804731963800, 7694644696200,
                                                                      10142940735900, 13298522298180, 17345898649800,
                                                                      22512762077400, 29078984349975, 37387265592825,
                                                                      47855699958816, 60992558771040, 77413632286320,
                                                                      97862516286480,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      155117520, 300540195, 565722720, 1037158320,
                                                                      1855967520, 3247943160, 5567902560, 9364199760,
                                                                      15471286560, 25140840660, 40225345056, 63432274896,
                                                                      98672427616, 151532656696, 229911617056, 344867425584,
                                                                      511738760544, 751616304549, 1093260079344,
                                                                      1575580702584, 2250829575120, 3188675231420,
                                                                      4481381406320, 6250347750920, 8654327655120,
                                                                      11899700525790, 16253249498640, 22057981462440,
                                                                      29752626158640, 39895566894540, 53194089192720,
                                                                      70539987842520, 93052749919920, 122131734269895,
                                                                      159518999862720, 207374699821536, 268367258592576,
                                                                      345780890878896,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      601080390, 1166803110, 2203961430, 4059928950,
                                                                      7307872110, 12875774670, 22239974430, 37711260990,
                                                                      62852101650, 103077446706, 166509721602, 265182149218,
                                                                      416714805914, 646626422970, 991493848554,
                                                                      1503232609098, 2254848913647, 3348108992991,
                                                                      4923689695575, 7174519270695, 10363194502115,
                                                                      14844575908435, 21094923659355, 29749251314475,
                                                                      41648951840265, 57902201338905, 79960182801345,
                                                                      109712808959985, 149608375854525, 202802465047245,
                                                                      273342452889765, 366395202809685, 488526937079580,
                                                                      648045936942300, 855420636763836, 1123787895356412,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      2333606220, 4537567650, 8597496600, 15905368710,
                                                                      28781143380, 51021117810, 88732378800, 151584480450,
                                                                      254661927156, 421171648758, 686353797976,
                                                                      1103068603890, 1749695026860, 2741188875414,
                                                                      4244421484512, 6499270398159, 9847379391150,
                                                                      14771069086725, 21945588357420, 32308782859535,
                                                                      47153358767970, 68248282427325, 97997533741800,
                                                                      139646485582065, 197548686920970, 277508869722315,
                                                                      387221678682300, 536830054536825, 739632519584070,
                                                                      1012974972473835, 1379370175283520, 1867897112363100,
                                                                      2515943049305400, 3371363686069236,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      9075135300, 17672631900, 33578000610, 62359143990,
                                                                      113380261800, 202112640600, 353697121050, 608359048206
                                                                      , 1029530696964, 1715884494940, 2818953098830,
                                                                      4568648125690, 7309837001104, 11554258485616,
                                                                      18053528883775, 27900908274925, 42671977361650,
                                                                      64617565719070, 96926348578605, 144079707346575,
                                                                      212327989773900, 310325523515700, 449972009097765,
                                                                      647520696018735, 925029565741050, 1312251244423350,
                                                                      1849081298960175, 2588713818544245, 3601688791018080,
                                                                      4981058966301600, 6848956078664700, 9364899127970100,
                                                                  }
                                                              ,
                                                              new ulong[]
                                                                  {
                                                                      35345263800, 68923264410, 131282408400, 244662670200,
                                                                      446775310800, 800472431850, 1408831480056,
                                                                      2438362177020, 4154246671960, 6973199770790,
                                                                      11541847896480, 18851684897584, 30405943383200,
                                                                      48459472266975, 76360380541900, 119032357903550,
                                                                      183649923622620, 280576272201225, 424655979547800,
                                                                      636983969321700, 947309492837400, 1397281501935165,
                                                                      2044802197953900, 2969831763694950, 4282083008118300,
                                                                      6131164307078475, 8719878125622720, 12321566916640800,
                                                                      17302625882942400, 24151581961607100,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      137846528820, 269128937220, 513791607420, 960566918220
                                                                      , 1761039350070, 3169870830126, 5608233007146,
                                                                      9762479679106, 16735679449896, 28277527346376,
                                                                      47129212243960, 77535155627160, 125994627894135,
                                                                      202355008436035, 321387366339585, 505037289962205,
                                                                      785613562163430, 1210269541711230, 1847253511032930,
                                                                      2794563003870330, 4191844505805495, 6236646703759395,
                                                                      9206478467454345, 13488561475572645, 19619725782651120
                                                                      , 28339603908273840, 40661170824914640,
                                                                      57963796707857040,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      538257874440, 1052049481860, 2012616400080,
                                                                      3773655750150, 6943526580276, 12551759587422,
                                                                      22314239266528, 39049918716424, 67327446062800,
                                                                      114456658306760, 191991813933920, 317986441828055,
                                                                      520341450264090, 841728816603675, 1346766106565880,
                                                                      2132379668729310, 3342649210440540, 5189902721473470,
                                                                      7984465725343800, 12176310231149295, 18412956934908690
                                                                      , 27619435402363035, 41107996877935680,
                                                                      60727722660586800, 89067326568860640,
                                                                      129728497393775280,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      2104098963720, 4116715363800, 7890371113950,
                                                                      14833897694226, 27385657281648, 49699896548176,
                                                                      88749815264600, 156077261327400, 270533919634160,
                                                                      462525733568080, 780512175396135, 1300853625660225,
                                                                      2142582442263900, 3489348548829780, 5621728217559090,
                                                                      8964377427999630, 14154280149473100, 22138745874816900
                                                                      , 34315056105966195, 52728013040874885,
                                                                      80347448443237920, 121455445321173600,
                                                                      182183167981760400, 271250494550621040,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      8233430727600, 16123801841550, 30957699535776,
                                                                      58343356817424, 108043253365600, 196793068630200,
                                                                      352870329957600, 623404249591760, 1085929983159840,
                                                                      1866442158555975, 3167295784216200, 5309878226480100,
                                                                      8799226775309880, 14420954992868970, 23385332420868600
                                                                      , 37539612570341700, 59678358445158600,
                                                                      93993414551124795, 146721427591999680,
                                                                      227068876035237600, 348524321356411200,
                                                                      530707489338171600,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      32247603683100, 63205303218876, 121548660036300,
                                                                      229591913401900, 426384982032100, 779255311989700,
                                                                      1402659561581460, 2488589544741300, 4355031703297275,
                                                                      7522327487513475, 12832205713993575, 21631432489303455
                                                                      , 36052387482172425, 59437719903041025,
                                                                      96977332473382725, 156655690918541325,
                                                                      250649105469666120, 397370533061665800,
                                                                      624439409096903400, 972963730453314600,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      126410606437752, 247959266474052, 477551179875952,
                                                                      903936161908052, 1683191473897752, 3085851035479212,
                                                                      5574440580220512, 9929472283517787, 17451799771031262,
                                                                      30284005485024837, 51915437974328292,
                                                                      87967825456500717, 147405545359541742,
                                                                      244382877832924467, 401038568751465792,
                                                                      651687674221131912, 1049058207282797712,
                                                                      1673497616379701112,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      495918532948104, 973469712824056, 1877405874732108,
                                                                      3560597348629860, 6646448384109072, 12220888964329584,
                                                                      22150361247847371, 39602161018878633,
                                                                      69886166503903470, 121801604478231762,
                                                                      209769429934732479, 357174975294274221,
                                                                      601557853127198688, 1002596421878664480,
                                                                      1654284096099796392, 2703342303382594104,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      1946939425648112, 3824345300380220, 7384942649010080,
                                                                      14031391033119152, 26252279997448736,
                                                                      48402641245296107, 88004802264174740,
                                                                      157890968768078210, 279692573246309972,
                                                                      489462003181042451, 846636978475316672,
                                                                      1448194831602515360, 2450791253481179840,
                                                                      4105075349580976232,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      7648690600760440, 15033633249770520, 29065024282889672
                                                                      , 55317304280338408, 103719945525634515,
                                                                      191724747789809255, 349615716557887465,
                                                                      629308289804197437, 1118770292985239888,
                                                                      1965407271460556560, 3413602103063071920,
                                                                      5864393356544251760,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      30067266499541040, 59132290782430712,
                                                                      114449595062769120, 218169540588403635,
                                                                      409894288378212890, 759510004936100355,
                                                                      1388818294740297792, 2507588587725537680,
                                                                      4472995859186094240, 7886597962249166160,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      118264581564861424, 232714176627630544,
                                                                      450883717216034179, 860778005594247069,
                                                                      1620288010530347424, 3009106305270645216,
                                                                      5516694892996182896, 9989690752182277136,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      465428353255261088, 916312070471295267,
                                                                      1777090076065542336, 3397378086595889760,
                                                                      6406484391866534976, 11923179284862717872,
                                                                  },
                                                              new ulong[]
                                                                  {
                                                                      1832624140942590534, 3609714217008132870,
                                                                      7007092303604022630, 13413576695470557606,
                                                                  },
                                                              new ulong[] {7219428434016265740, 14226520737620288370,},
                                                          };

        private static readonly List<List<BigInteger>> _bigIntegerValues = new List<List<BigInteger>>();
        private static readonly ReaderWriterLockSlim _lock = new ReaderWriterLockSlim();
    }
}